#include <stdio.h>
#include <malloc.h>
#include <string.h>

typedef struct tree_node *tree_ptr;

struct tree_node {
    int element;
    tree_ptr left;
    tree_ptr right;
};

typedef tree_ptr SEARCH_TREE;

SEARCH_TREE make_null(void) {
    return NULL;
}

void fatal_error(char *s) {
    printf("fatal error %s", s);
}

void error(char *s) {
    printf("fatal error %s", s);
}

int powerOfTwo(int exponent) {
    int result = 1;
    int i;
    for (i = 0; i < exponent; i++) {
        result *= 2;
    }
    return result;
}

tree_ptr insert(int x, SEARCH_TREE T) {
    if (T == NULL) {
        T = (SEARCH_TREE) malloc(sizeof(struct tree_node));
        if (T == NULL) {
            fatal_error("Out of space!!!");
        } else {
            T->element = x;
            T->left = T->right = NULL;
        }
    } else {
        if (x < T->element) {
            T->left = insert(x, T->left);
        } else if (x > T->element) {
            T->right = insert(x, T->right);
        }
    }
    return T;
}

tree_ptr initialize(const int *arr, int depth, int offset, SEARCH_TREE T) {
    if (depth > 3) {
        return T;
    }
    if (T == NULL) {
        T = insert(arr[0], T);
        initialize(arr, 1, 0, T);
    } else {
        int depth_node_num = powerOfTwo(depth);
        int depth_parent_node_num = powerOfTwo(depth - 1);
        int now_offset = offset + depth_parent_node_num;
        int len = now_offset + depth_node_num;
        printf("depth=%d, offset=%d, depth_node_num=%d \n", depth, now_offset, depth_node_num);
        for (int i = now_offset; i < len; i++) {
            T = insert(arr[i], T);
        }
        initialize(arr, ++depth, now_offset, T);
    }
}

void print_tree(int depth, SEARCH_TREE T, int nowDepth) {
    int depth_node_num = powerOfTwo(depth);
    char p[100] = "";
    for (int j = 0; j < depth_node_num; j++) {
        strcat(p, "-");
    }
    for (int i = 0; i < depth; i++) {
        printf("%s\n", p);
    }
}

void inorderTraversal(SEARCH_TREE T, int nowDepth) {
    if (T == NULL) {
        return;
    }
    inorderTraversal(T->left, ++nowDepth);
    printf("%d - %d\n", T->element, nowDepth);
    inorderTraversal(T->right, nowDepth);
}

tree_ptr find(int x, SEARCH_TREE T) {
    if (T == NULL)
        return NULL;
    if (x < T->element)
        return find(x, T->left);
    else if (x > T->element)
        return find(x, T->right);
    else
        return T;
}

tree_ptr find_min(SEARCH_TREE T) {
    if (T == NULL)
        return NULL;
    else if (T->left == NULL)
        return T;
    else
        return find_min(T->left);
}

//? non-recursive
tree_ptr find_max(SEARCH_TREE T) {
    if (T != NULL) {
        while (T->right != NULL)
            //! T->right = T->right->right will be make changes
            T = T->right;
    }
    return T;
}

tree_ptr delete(int x, SEARCH_TREE T) {
    tree_ptr tmp_cell, child;
    if (T == NULL) {
        error("Element not found");

    } else if (x < T->element) {
        T->left = delete(x, T->left);

    } else if (x > T->element) {
        T->right = delete(x, T->right);

    } else if (T->left && T->right) {
        //? Replace with smallest in right subtree
        tmp_cell = find_min(T->right);
        //? Save the node, just replace the key
        T->element = tmp_cell->element;
        T->right = delete(T->element, T->right);

    } else {
        //? delete immediately, node is a leaf or has one child
        tmp_cell = T;
        if (T->left == NULL) {
            T = T->right;
        } else if (T->right == NULL) {
            T = T->left;
        }
        free(tmp_cell);
    }
    return T;
}

int main() {
    printf("Done\n");
    /**
     * !*******6********
     * !   2       8
     * ! 1   4   7   9
     * !0 0 3 5 0 0 0 0
     */
    int arr[] = {6, 2, 8, 1, 4, 7, 9, 0, 0, 3, 5, 0, 0, 0, 0};
    SEARCH_TREE T = initialize(arr, 0, 0, NULL);
    print_tree(4, T, 0);
    inorderTraversal(T, 0);
    return 0;
}
